import javafx.util.Pair;
import java.util.ArrayList;
import java.util.List;

public class MaximumWidthOfBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {
        // 因为题目给的树节点范围是 [1, 3000], 因此不用判断 root 是否为空

        List<Pair<TreeNode, Integer>> list = new ArrayList<>();
        list.add(new Pair<TreeNode, Integer>(root, 0));
        int width = 0;

        while (!list.isEmpty()) {
            // 取出队首队尾元素, 更新宽度
            Pair<TreeNode, Integer> head = list.get(0);
            Pair<TreeNode, Integer> last = list.get(list.size() - 1);
            width = Math.max(width, last.getValue() - head.getValue() + 1);

            // 用一个新的数组存放下一层节点
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            // 遍历下一层节点
            for (Pair<TreeNode, Integer> child : list) {
                TreeNode cur = child.getKey();
                Integer index = child.getValue();
                if (cur.left != null) {
                    tmp.add(new Pair<TreeNode, Integer>(cur.left, 2 * index + 1));
                }
                if (cur.right != null) {
                    tmp.add(new Pair<TreeNode, Integer>(cur.right, 2 * index + 2));
                }
            }
            // 用新数组覆盖旧数组
            list = tmp;
        }
        return width;
    }
}
